20.3 Linear Probing


What's Linear Probing?

	a method for resolving collisions in a hash table


How do you insert an item in a hash table using Linear Probing?

	sequentially scan the array until an empty cell is found
	wrap-around from the last position to the first


Show the result of inserting 2, 7, 3, 8 into a hash table of size 5.



How do you find an item in a hash table using Linear Probing?

	follow the same sequence as insert
	if you reach an empty slot, the item is not in the table


Show the result of finding 8 and 9 in the previous hash table.



Classwork
You may work with a partner.
Show the result of inserting 7, 6, 1, 2 into a hash table of size 5.



How do you delete an item from a hash table using Linear Probing?

	you must use lazy deletion
	mark items deleted





Analysis of Linear Probing


What's the Load Factor of a hash table?

	lambda
	the fraction of the table that is full
	ranges from 0 to 1


Given a hash table with load factor lambda, what's the probability of
hitting an empty cell with one probe?

	1-lambda


Assuming that probes are independent (not valid), how many probes (on
average) are needed to find an empty slot in the table?

	1/(1-lambda)
	2 probes in a half-full table
	10 probes in a 90%-full table


Why are the probes not independent?
What's Primary Clustering?

	large blocks of occupied cells are formed
	insertions at indexes in the cluster are expensive


Assuming that probes are not independent, how many probes (on average)
are needed to find an empty slot in the table?

	(1 + 1/(1-lambda)^2) / 2
	2.5 probes in a half-full table
	50 probes in a 90%-full table




Does Linear Probing work well enough to use in practice?

	yes
	if you keep the load factor low (lambda < 0.5)
	then linear probing works well
	if you could remove primary clustering
	you'd only save 0.5 probe on insert, 0.1 probe on find


What's a good Load Factor to use with Linear Probing?

	keep the load factor low, lambda < 0.5